#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void PrintArry(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//递归归并
void _MegerSort(int* a, int left, int right,int*temp)
{
	if (right <= left)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	_MegerSort(a, left, mid, temp);
	_MegerSort(a, mid + 1, right, temp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2])
		{
			temp[i++] = a[begin2++];
		}
		else
		{
			temp[i++] = a[begin1++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	memcpy(a + left, temp + left, sizeof(int) * (right - left + 1));
}


//归并完再一起拷贝
void _MegerSortNonR1(int* a, int n,int* temp)
{
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;



			//修正路线
			//end1越界，不再归并
			if (end1 >= n)
			{
				end1 = n - 1;
				//把越界的部分修正为不存在的区间
				begin2 = n;
				end2 = n - 1;
			}
			//end1不越界，begin2越界，不再归并
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			//end2越界，其他都不越界，继续归并，修正end2
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			printf("[%d,%d],[%d,%d]", begin1, end1, begin2, end2);

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					temp[j++] = a[begin1++];
				}
				else
				{
					temp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = a[begin2++];
			}

		}
		printf("\n");
		memcpy(a, temp, sizeof(int) * n);
		gap *= 2;
	}
}

//归并一组拷贝一组
void _MegerSortNonR2(int* a, int n, int* temp)
{
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int j = i;

			//修正路线
			//end1越界||end1不越界，begin2越界，不再归并
			if (end1 >= n||begin2>=n)
			{
				break;
			}
			//end1不越界，begin2越界，不再归并
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			printf("[%d,%d],[%d,%d]", begin1, end1, begin2, end2);

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] > a[begin2])
				{
					temp[j++] = a[begin2++];
				}
				else
				{
					temp[j++] = a[begin1++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				temp[j++] = a[begin2++];
			}

			memcpy(a + i, temp + i, sizeof(int) * (end2 - i + 1));

		}
		printf("\n");
		gap *= 2;
	}
}


void MegerSort(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail\n");
		return;
	}

	//_MegerSort(a, 0, n - 1, temp);
	_MegerSortNonR1(a, n, temp);

	free(temp);

}

int main()
{
	int a[] = { 6,1,2,7,9,3,4,5,10 };
	PrintArry(a, sizeof(a) / sizeof(a[0]));

	MegerSort(a, sizeof(a) / sizeof(a[0]));
	PrintArry(a, sizeof(a) / sizeof(a[0]));

	return 0;

}